
"""
// 第一个大于x的元素的下标， [0, n]
int upper_bound(int A[], int left, int right, int x) {
  int mid;
  // 注意没有等于。
  while (left < right) {
    // 就本问题而言，左边的一半不满足，右边的一半满足条件（这里的一半并不是
    // 真的一半）。
    mid = (left + right) / 2;
    if (A[mid] > x) {
      // 满足了条件，说明我们在右边满足条件的一半，但是我们要找的是满足条件的
      // 第一个，即两边的分界线，所以要向左去。
      right = mid;
    } else {
      // 中点不满足条件，说明我们还在左边不满足的一半，所以去右边。
      left = mid + 1;
    }
    // 直到区间只有一个元素，说明我们已经到了边界线，并且是满足条件的一侧。
    // left-1 就是最后一个小于等于x的元素。
  }
  // 这种模板求出来的，就是第一个满足条件的下标，也就是两边分界线靠满足条件的一侧。
  return left;
}
"""


def FindInsertPosition(A, left, right, x):
    """
    Find the first element in A that is greater than x.
    x should be inserted at this position.
    """
    while left < right:
        mid = (left+right)//2
        if A[mid] > x:
            right = mid
        else:
            left = mid+1
    return left


def Insert(A: list, pos, x):
    A.insert(pos, x)


def ModInsertSort(A, n):
    for i in range(1, n):
        x = A[i]  # x是待插入元素。
        left = 0  # left，right是二分区间。
        right = i  # 注意这里，一定要包括原有区间的右端点+1的位置。
        # 用二分法检索插入位置。
        while left < right:
            mid = (left+right)//2
            if A[mid] > x:
                right = mid
            else:
                left = mid+1
        pos = left  # 找到了插入位置。
        # 元素后移，为x腾出位置。
        for j in range(i, pos, -1):
            A[j] = A[j-1]
        A[pos] = x  # x插入到正确位置。


def InsertSort(A, n):
    for i in range(1, n):
        x = A[i]
        j = i-1
        while j >= 0 and A[j] > x:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = x


def main():
    import random
    A = list(range(6))
    B = A.copy()
    random.shuffle(A)
    ModInsertSort(A, len(A))
    assert A == B, f'A={A}, B={B}'


for i in range(10000):
    main()
